CF Round 729 div2补题

Codeforces Round 729 div2

D

题目大意

给一个序列$a$和一个空集$T$，序列$a$的元素有两种形式，分别代表对集合 $T$ 不同的操作：

• + x，向多重集合 $T$ 中插入一个元素$x$
• -，删除多重集合中最小的元素，如果是空集，则什么都不做。

考虑$a$的所有子序列，这些子序列分别对 $T$ 进行操作，各自可以得到最终的集合 $T'$ ，求所有的 $ T'$ 的所有元素的和。

思路

能看出很多重复计算，所以容易想到dp。

dp时不是统计每个子序列的和，而是统计每个元素在多少个子序列中出现过（考虑每个元素的贡献次数），这算是一个比较常用的技巧。

考虑a[i]如何才能贡献在一个序列中：在选了a[i]之后，后面出现的-不能把a[i]排除掉。

即在a[i]之前出现的小于等于a[i]的数的个数随着选择a[i]之后元素时，始终保证存在小于等于a[i]的数。

下面是dp的设计：

• 设dp[i][j]的集合是分析到第i个元素为止，目前维护的集合$T$中还剩下j个比x（我们枚举所有的x = a[i]）小的数的子序列的集合

• dp[i][j]表示的集合的属性是集合的大小

• 考虑第i个元素是什么：

  • 第i个元素是-，则dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][j] ，这两项分别代表选择这个-以及不选这两种情况。另外，如果是j == 0且当前还没枚举到x那个位置，那么还可以再加一个dp[i - 1][j]，因为删了也不影响。
  • 第i个元素是+ y，考虑x和y的大小关系
    • y > x （先比较值，值相同比较rank，rank小的按照大于处理），则dp[i][j] = dp[i - 1][j] + dp[i - 1][j] ，两项分别代表不选和选。
    • y < x，则dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]，两项分别代表不选和选，如果这个时候j == 0 ，那么就不能算选择该数的情况，不然就转移到状态-1了，而状态-1也代表了我们目标的那个数已经被删掉了。
    • y == x，恰好是我们要选的这个元素，那只能选，所以dp[i][j] = dp[i - 1][j] 。

• 初始化的考虑：

  • 本题的边界情况是dp[i][0] ，其含义是分析到第i个元素为止，目前维护的集合$T$中没有比x小的子序列的集合。显然dp[0][0] = 1，为空集。

• 答案的计算：

  • 显然，对于x来说，算出来的每个dp[n][i]中的序列都是包含有x的，所以每枚举一个x，就可以贡献$\sum_{i = 0} ^{n}x \times dp[n][i]$

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 510;
const int M = 510;
const int mod = 998244353;

typedef long long ll;

ll n, dp[N][M], a[N];
bool is_del[N];

int main() {
    scanf("%lld", &n);

    char op[2];
    for (int i = 1; i <= n; i++) {
        scanf("%s", op);
        if (op[0] == '+') {
            scanf("%lld", &a[i]);
        } else {
            is_del[i] = true;
        }
    }

    ll ans = 0;
    for (int k = 1; k <= n; k++) {
        if (is_del[k]) continue;

        ll x = a[k];
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (is_del[i]) {
                    dp[i][j] = (dp[i - 1][j + 1] + dp[i - 1][j]) % mod;
                    if (i < k && j == 0) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
                    }
                } else {
                    if (a[i] < x) {
                        dp[i][j] += dp[i - 1][j];
                        if (j >= 1) {
                            dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
                        }
                    } else if (a[i] > x) {
                        dp[i][j] = (dp[i - 1][j] + dp[i - 1][j]) % mod;
                    } else {
                        if (k == i) {
                            dp[i][j] = dp[i - 1][j] % mod;
                        } else if (i < k) {
                            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j]) % mod;
                        } else {
                            dp[i][j] = dp[i - 1][j];
                            if (j >= 1) {
                                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
                            }
                        }
                    }
                }
                // printf("(%d, %d) = %lld\n", i, j, dp[i][j]);
            }
        }

        for (int i = 0; i <= n; i++) {
            ans = (ans + dp[n][i] * x) % mod;
        }
    }

    printf("%lld\n", ans);

    return 0;
}